A kernel is the essential center of a computer operating system, the core that provides basic services for all other parts of the operating system. A kernel can be contrasted with a shell, the outermost part of an operating system that interacts with user commands.
Typically, a kernel (or any comparable center of an operating system) comprises programming code that runs on a central processing unit (CPU) and includes an interrupt handler that handles all requests or completed input/output (I/O) operations that compete for the kernel's services, a scheduler that determines which programs use the kernel processing time and an order of use, and a supervisor that allows usage of the CPU to each task when the task is scheduled. A kernel may also include a manager of the operating system address spaces in memory or storage, sharing the address spaces among all components and other users of the services of the kernel. The services of a kernel may be requested by other parts of the operating system, or by applications, through a specified set of program interfaces sometimes known as system calls.
Most modern real-time kernels provide a preemptive, priority-based scheduling algorithm. With a preemptive, priority-based scheduling algorithm, each task has a priority and the kernel insures that CPU usage is allocated to the highest priority task that is ready to run. This scheduling algorithm is preemptive in that, if a task that has a higher priority than the current task becomes ready to run, the kernel immediately saves the context of the current task and switches to the context of the higher priority task. The priority of a given task may be chosen to reflect both the urgency and the importance of the given task within a processing system. Although it is possible to change the priority of the task after initial creation, many processing systems choose to use static task priority assignments, which are unlikely to reflect the processing system's changing CPU load and demand.
In a complex and busy real-time system, demand for CPU usage is often in excess of 100%. When this occurs, some (high priority) tasks may dominate usage of the CPU, while some (low priority) tasks are starved, i.e., receive no usage of the CPU. It has been recognized for some time that a scheduling model different from static task priority assignment would be beneficial to modern systems. One solution to the problem of starved low priority tasks is to reassign the priority of a starved low-priority task that is required to receive some usage of the CPU. Such a reassignment shuffles one or more of the tasks previously dominating usage of the CPU down a list of tasks organized by priority. However, such shuffling of the static task priorities often fails to solve the problem, in that a new set of tasks may be starved for CPU usage. Finding an ideal hierarchy of task priorities is fundamentally difficult in a complex system and is often impossible in a system where the demands are diverse over time.
Some alternative systems have employed dynamic adjustment of task priorities wherein task priorities are adjusted over time to accommodate the changing demands of the system.
In a system employing “Normal Proportional Share Scheduling”, tasks are guaranteed a percentage of the task level CPU usage, relative to each other. Only one task is allowed to run at any given time. A scheduling algorithm chooses a task to run, and the chosen task runs with a frequency or duration (depending upon the algorithm) in proportion to the percentage guaranteed to the chosen task.
The Normal Proportional Share Scheduling model may be seen to be too static, to lack respect for changing needs and to lack the ability to accommodate urgent demands. Latency, a delay before a given task is provided with an opportunity to run, may be seen to become an issue, even in underload conditions. Furthermore, the Normal Proportional Share Scheduling model manages the system even when the system does not require managing, i.e., when demand for CPU usage is less than 100%.
A model called “Inverse Proportional Share Scheduling” is a derivative of Normal Proportional Share Scheduling. Unlike Normal Proportional Share Scheduling, which attempts to avoid starvation by guaranteeing CPU usage to each task, Inverse Proportional Share Scheduling limits the CPU usage of each task. Tasks take turns serving a penalty (i.e., being prevented from running). The length of the penalty associated with a given task is proportional to the penalties of the other participating tasks.
Like Normal Proportional Share Scheduling, the Inverse Proportional Share Scheduling model may be seen to be too static, to lack respect for changing needs and to lack the ability to accommodate urgent demands. Latency may be seen to become an issue, even in underload conditions, and the Inverse Proportional Share Scheduling model manages the system even when the system does not require managing.
In a pure application-based solution, the system relies upon applications to develop their own solutions to scheduling problems, employing their own custom algorithms. However, such a solution relies upon the “good nature” of the applications, which may not be wise. Additionally, a single, system-wide solution may be seen to be more efficient and cost effective than multiple, application-based solutions.
In an approach based on the pure application-based solution, but with the addition of kernel assistance, a given application may regularly signal to the scheduler that the given application may give up the CPU at that moment, without interrupting critical work. A set of primitives may be provided by the kernel to facilitate such signaling. The given application has incentive to provide these regular signals, as the signals provide the scheduler with an ability to avoid interrupting the given application at an inconvenient time.
Such an approach, while similar to the pure application-based solution, relies upon primitives and measurements provided by the kernel to ensure correct execution. The approach has an advantage over the pure application-based solution in that some part of the solution is shared by the system, reducing the overhead to the system. However, the approach still relies upon the good nature of the applications.
In so-called “Modal” solutions, when the demand for the CPU grows beyond 100%, the system switches from one scheduling mode to another scheduling mode. For example, the system could switch from purely static, priority-based scheduling, a model which favors urgency, to Normal Proportional Share Scheduling, which favors importance in an overload situation. In this sense, each task has two priorities, one for urgency and one for importance.
Unfortunately, it has been found that modal solutions fail to work very well due to a difficulty in identifying the overload prioritization. The set of priorities for the overloaded state depends upon the cause of the overload condition. Anything that causes CPU demand in excess of 100% for an extended period of time could be considered to be causing overload. To be effective, a prioritization must be defined for each possible cause of overload, and each of their permutations. For systems wherein the number of possible overload causes is large, such prioritization definition becomes unmanageable.
Another approach calls for “call back registration” for dealing with timer extend requirements. Typically, several applications deal with situations wherein a client is waiting for a response. Often the application never receives sufficient CPU time to generate a response to the client and the client times out. The approach offers a scheduler a low cost mechanism to inform a given application that:    a) it is recognized that you haven't received CPU time for X time-units;    b) it is recognized that that your client is about to timeout;    c) you are about to receive some CPU time; and    d) this is your opportunity to request that your client extend its timeout.
However, while this approach may work with applications of the type that act as servers, this approach may not work with applications of the type for which only the final result is appropriate for the client. For applications of the latter type, if the application is to be allocated CPU usage, it may be preferred that the application use the allocated CPU usage to work on the final result, rather than forming a request to extend a timeout.
In a “Strictly Constrained Ordered Scheduling” approach, the scheduler is pre-programmed with a fixed task scheduling order for a particular environment. Since the approach relies upon a priori knowledge of the system, this approach is generally used for a small subset of systems, including hard real-time systems such as engine management, and is not broadly applicable.
A “Deadline Driven” scheduling model requires that task priorities be dynamically computed and adjusted to meet hard deadlines. Although a variety of methods are employed to compute task priorities from a set of deadlines, the earliest-deadline-first algorithm is common. In this scheduling model, the task with the earliest deadline has the highest priority and the task with the latest deadline has the lowest priority. This scheduling model relies upon a priori knowledge about the deadlines of each task in the system. While all scheduling models depend upon some a priori knowledge to some extent, deadline driven models require a greater understanding of the demands of a system and are typically only useful in hard real-time systems.
Clearly, a new scheduling model is required that addresses shortcomings of existing scheduling models.